package leetcode.code0147;

import leetcode.IDebug;
import leetcode.helper.tree.ListNode;

//执行用时：21 ms, 在所有 Java 提交中击败了33.78%的用户
//
//内存消耗：41.5 MB, 在所有 Java 提交中击败了5.12%的用户
//
//通过测试用例：19 / 19
public class Solution implements IDebug {

	public ListNode insertionSortList(ListNode head) {
		ListNode ans = new ListNode();
		ListNode cur = head;
		head = head.next;
		cur.next = null;
		ans.next = cur;
		while (head != null) {
			cur = head;
			head = head.next;
			cur.next = null;
			ListNode p = ans.next;
			ListNode last = ans;
			while (p != null) {
				if (cur.val < p.val) {
					cur.next = last.next;
					last.next = cur;
					break;
				}
				if (p.next == null) {
					p.next = cur;
					break;
				}
				last = p;
				p = p.next;
			}
		}
		return ans.next;
	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
